package likou.tanxin;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/07 10:58
 */
public class _881 {
    public static void main(String[] args) {
        System.out.println(numRescueBoats(new int[]{5, 1, 4, 2}, 6));
    }

    public static int numRescueBoats(int[] people, int limit) {
        int daan = 0;
        int end = people.length - 1;
        Arrays.sort(people);
        for (int i = 0; i <= end; i++) {
            int que = limit - people[i];
            if (que >= people[i]) {
                while (end > i) {
                    if (people[end] <= que) {
                        people[end] = -1;
                        end--;
                        break;
                    }
                    end--;
                }
            }
            people[i] = -1;
            daan++;
        }
        if (end != people.length - 1) {
            for (int i = 0; i < people.length; i++) {
                if (people[i] != -1) {
                    daan++;
                }
            }
        }
        return daan;
    }
    //别想着一次性处理太多数据
    public int numRescueBoats2(int[] people, int limit) {
        int[] buckets = new int[limit + 1];
        for (int p : people) buckets[p]++;
        int left = 0;
        int right = buckets.length - 1;
        int res = 0;
        while (left <= right) {
            while (left <= right && buckets[left] == 0) left++;
            while (left <= right && buckets[right] == 0) right--;
            if (buckets[left] <= 0 && buckets[right] <= 0) break;
            res++;
            if (left + right <= limit) buckets[left]--;
            buckets[right]--;
        }
        return res;
    }
}
